DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2016.14

Computing the L1 Geodesic Diameter and Center of a Polygonal Domain

Authors: Sang Won Bae, Matias Korman, Joseph S. B. Mitchell, Yoshio Okamoto, Valentin Polishchuk, and Haitao Wang

Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

Abstract

For a polygonal domain with h holes and a total of n vertices, we present algorithms that compute the L_1 geodesic diameter in O(n^2+h^4) time and the L_1 geodesic center in O((n^4+n^2 h^4)*alpha(n)) time, where alpha(.) denotes the inverse Ackermann function. No algorithms were known for these problems before. For the Euclidean counterpart, the best algorithms compute the geodesic diameter in O(n^{7.73}) or O(n^7(h+log(n))) time, and compute the geodesic center in O(n^{12+epsilon}) time. Therefore, our algorithms are much faster than the algorithms for the Euclidean problems. Our algorithms are based on several interesting observations on L_1 shortest paths in polygonal domains.

Cite as

Sang Won Bae, Matias Korman, Joseph S. B. Mitchell, Yoshio Okamoto, Valentin Polishchuk, and Haitao Wang. Computing the L1 Geodesic Diameter and Center of a Polygonal Domain. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{wonbae_et_al:LIPIcs.STACS.2016.14,
  author =	{Won Bae, Sang and Korman, Matias and Mitchell, Joseph S. B. and Okamoto, Yoshio and Polishchuk, Valentin and Wang, Haitao},
  title =	{{Computing the L1 Geodesic Diameter and Center of a Polygonal Domain}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{14:1--14:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Ollinger, Nicolas and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.14},
  URN =		{urn:nbn:de:0030-drops-57151},
  doi =		{10.4230/LIPIcs.STACS.2016.14},
  annote =	{Keywords: geodesic diameter, geodesic center, shortest paths, polygonal domains, L1 metric}
}

Search Results

Documents authored by Won Bae, Sang

Computing the L1 Geodesic Diameter and Center of a Polygonal Domain

Abstract

Cite as

Thanks for your feedback!

Could not send message